#pragma once
//template<typename T = char>
template<typename T>
class Stack
{
public:
	Stack(size_t capacity = 4)
		:_a(nullptr)
		, _top(0)
		, _capacity(0)
	{
		if (capacity > 0)
		{
			_a = new T[capacity];
			_capacity = capacity;
			_top = 0;
	}
	}

	//Stack(size_t capacity = 0)
	//{
	//	if (capacity > 0)
	//	{
	//		_a = new T[capacity];
	//		_capacity = capacity;
	//		_top = 0;
	//	}
	//}

	~Stack()
	{
		delete[] _a;
		_a = nullptr;
		_capacity = _top = 0;
	}

	void Push(const T& x);

	void Pop()
	{
		assert(_top > 0);
		--_top;
	}

	bool Empty()
	{
		return _top == 0;
	}

	const T& Top()
	{
		assert(_top > 0);

		return _a[_top - 1];
	}
private:
	T* _a = nullptr;
	size_t _top = 0;
	size_t _capacity = 0;
};

template<class T>
void Stack<T>::Push(const T& x)
{
	if (_top == _capacity)
	{
		size_t newCapacity = _capacity == 0 ? 4 : _capacity * 2;
		// 1、开新空间
		// 2、拷贝数据
		// 3、释放旧空间
		T* tmp = new T[newCapacity];
		if (_a)
		{
			memcpy(tmp, _a, sizeof(T) * _top);
			delete[] _a;
		}

		_a = tmp;
		_capacity = newCapacity;
	}

	_a[_top] = x;
	++_top;
}